//https://mp.weixin.qq.com/s?__biz=MjM5OTM4MDgwOQ==&mid=2449413214&idx=1&sn=9ea3a106592d73af0f06e7b8f32ba57d&chksm=b337e67884406f6e6e0ac76351fafe2fe07bd61210cfef3ad466a41549c77d1b71794eb39353&mpshare=1&scene=1&srcid=0713Ob1q48fjPiYlzsR5BoAE&sharer_sharetime=1594626444032&sharer_shareid=37d10083a282df9dd7c2bff05db81692&key=f3d9c59dc43281a79cefa9d3da4987f576a08dca7b86b02c954ae4620400e3660d8a796280f3787e51159b26257cc1693e912f8e97fdf2df3ab91f40f8f8aa41f78965e11b12f635be38faec71c786ec&ascene=1&uin=MTMzMjUyNDgxMA%3D%3D&devicetype=Windows+10+x64&version=62090529&lang=zh_CN&exportkey=A9npAU3Mm6k145wV9FqFNPM%3D&pass_ticket=ohLK0k6l3obuYe71RoCk0Yixvlb89rTTFjjpqbLQkyOT8D%2B8%2F0PDR8Sl2ZrOsLtT
/*

1.栈 Stack
Stack的特点是后进先出(last in first out). 生活中常见的Stack的例子比如一摞书,你最后放上去的那本你之后
会最先拿走;又比如浏览器的访问历史,当点击返回按钮,最后访问的网站最先从历史记录中弹出.
Stack一般具有以下方法:
1.push: 将一个元素推入栈顶
2.pop: 移除栈顶元素,并返回被移除的元素
3.peek: 返回栈顶元素
4.length: 返回栈中元素的个数
Javascript的Array天生具备了Stack的特性,但我们也可以从头实现一个Stack类:
*/
function Stack(){
  this.count = 0;
  this.storage = {};
  //元素推入栈顶
  this.push = function(value){
    this.storage[this.count] = value;
    this.count ++;
  }
  //移除栈顶元素并返回被移除的元素
  this.pop = function(){
    if(this.count === 0){
      return undefined;
    }
    this.count --;
    var result = this.storage[this.count];
    delete this.storage[this.count];
    return result;
  }
  //返回栈顶元素
  this.peek = function(){
    return this.storage[this.count - 1];
  }
  //栈中元素个数
  this.size = function(){
    return this.count;
  }

}
/*

2.队列 Queue
Queue和Stack有一些类似,不同的是Stack是先进后出,而Queue是先进先出.
Queue在生活中的例子比如排队上公交,排在第一个的总是最先上车;又比如打印机
的打印队列,排在前面的最先打印.

Queue一般具有以下常见方法:
1.enqueue: 入列,向队列尾部添加一个元素
2.dequeue: 出列,移除队列头部的一个元素并返回被移除的元素
3.front: 获取队列的第一个元素
4.isEmpty: 判断队列是否为空
5.size: 获取队列中元素的个数
Javascript中的Array已经具备了Queue的一些特性,所以我们可以借助Array
实现一个Queue类型:
*/
function Queue(){
  var collection = [];

  this.print = function(){
    console.log(collection);
  }

  this.enqueue = function(element){
    collection.push(element);
  }

  this.dequeue = function(){
    return collection.shift();
  }

  this.front = function(){
    return collection[0];
  }

  this.isEmpty = function(){
    return collection.length === 0;
  }

  this.size = function(){
    return collection.length;
  }
}
/*

3.优先队列 Priority Queue
Queue还有个升级版本,给每个元素赋予优先级,优先级高的元素入列时将排到
低优先级元素之前.区别主要是enqueue方法的实现:
*/
function PriorityQueue(){
  var collection = [];
  this.isEmpty = function(){
    return collection.length === 0;
  }
  this.print = function(){
    console.log(collection);
  }
  // this.push = function(element){
  //   collection.push(element);
  // }
  //省略其他代码
  this.enqueue = function(element){
    if(this.isEmpty()){
      collection.push(element);
    }else{
      var added = false;
      for(var i=0;i<collection.length;i++){
        if (element[1]<collection[i][1]){
          collection.splice(i,0,element);
          added = true;
          break;
        }
      }
      if(!added){
        collection.push(element);
      }
    }
  }
}
// 测试
var pQ = new PriorityQueue();
pQ.enqueue(['123ff',3]);
pQ.enqueue(['sd131',1]);
pQ.enqueue(['21f1r1',2]);
pQ.enqueue(['kkk1123',4]);
pQ.print();
/*
3.链表 Linked List
顾名思义,链表是一种链式数据结构,链上的每个节点包含两种信息:
节点本身的数据和指向下一个节点的指针.链表和传统的数组都是线性
的数据结构,存储的都是一个序列的数据,但也有很多区别,如下表:
--------------------------------------------------------------------------------
  比较维度    |   数组                      |   链表                               |
  内存分配    | 静态内存分配,编译时分配且连续    | 动态内存分配,运行时分配且不连续           |
  元素获取    | 通过Index获取,速度较快         | 通过遍历顺序访问,速度较慢               |
  添加删除元素 | 因为内存位置连续且固定,速度较慢   | 因为内存分配灵活,只有一个开销步骤,速度更快 |
  空间结构    | 可以是一维或者多维数组          | 可以是单向,双向或者循环链表              |
---------------------------------------------------------------------------------
*/
/*
一个单向链表通常具有以下方法:
1.size:返回链表中节点的个数
2.head:返回链表中的头部元素
3.add:向链表尾部增加一个节点
4.remove:删除某个节点
5.indexOf:返回某个节点的index
6.elementAt:返回某个index处的节点
7.addAt:在某个index处插入一个节点
8.removeAt:删除某个index处的节点
*/
// 单向链表的Javascript实现:

/**
 * 链表中的节点
 * @param element
 * @constructor
 */
function Node(element) {
  //节点中的数据
  this.element = element;
  //指向下一个节点的指针
  this.next = null;
}

function LinkedList(){
  var length = 0;
  var head = null;

  this.size = function(){
    return length;
  }

  this.head = function(){
    return head;
  }

  this.add = function(element){
    var node = new Node(element);
    if(head == null){
      head = node;
    }else{
      var currentNode = head;

      while(currentNode.next){
        currentNode = currentNode.next;
      }

      currentNode.next = node;
    }
    length++;
  }

  this.remove = function(element){
    var currentNode = head;
    var previousNode;
    if(currentNode.element === element){
      head = currentNode.next;
    }else{
      while(currentNode.element !== element){
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
  }

  this.isEmpty = function(){
    return length === 0;
  }

  this.indexOf = function(element){
    var currentNode = head;
    var index = -1;
    while(currentNode){
      index++;
      if(currentNode.element === element){
        return index;
      }
      currentNode = currentNode.next;
    }
    return -1;
  }

  this.elementAt = function(index){
    var currentNode = head;
    //5000
    var count = 0;
    while(count < index){
      count ++;
      currentNode =  currentNode.next;
    }
    return currentNode.element;
  }

  this.addAt = function(index,element){
    var node = new Node(element);
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;

    if(index>length){
      return false;
    }

    if(index === 0){
      node.next = currentNode;
      head = node;
    }else{
      while(currentIndex < index){
        currentIndex ++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      node.next = currentNode;
      previousNode.next = node;
    }
    length++;
  }

  this.removeAt = function(index){
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;
    if(index<0||index>=length){
      return null;
    }
    if(index===0){
      head = currentIndex.next;
    }else{
      while(currentIndex<index){
        currentIndex ++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length --;
    return currentNode.element;
  }
}
